package 树.递归;

/*
解题思路：
   这题使用递归解决。题目问的是有没有一条根节点到叶子节点的路径，
   这条路径上所有节点值相加等于目标和。 我们可以反向理解，从根节点加到叶子节点的值等于sum，
   就是满足条件的。那么我们既然有sum的值，我们就可以从根节点出发，
   每经过一个节点就用sum减去那个节点的值，直到叶子节点。这个时候再判断sum是不是为0.如果为0，
   证明这条路上节点值的和刚好等于sum。
*/
public class 路径总和_112 {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }

        if (root.left == null && root.right == null) {//当到达叶子节点的时候
            sum = sum - root.val;//到达了叶子节点，还要用sum减去叶子节点的值
            return sum == 0;//如果sum为0证明这条路线满足条件
        }

        boolean caseLeft = hasPathSum(root.left, sum - root.val);//遍历左子树，这时候sum应该更新为 “原来的sum减去了根节点的值”
        boolean caseRight = hasPathSum(root.right, sum - root.val);

        return caseLeft || caseRight;//只要左子树或者右子树有一棵树满足sum最后为0，那么就达到目标了，证明存在题目所要求的那么一条路径。  返回true
    }
}
